#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define OK 1
#define ERROR -1
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0
typedef int Status;

typedef char TElemType;
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode * lchild, *rchild;
}BiTNode, * BiTree;

typedef BiTree SElemType;
typedef struct StackNode
{
    SElemType data;
    struct StackNode * next;
}StackNode, * Stack;
typedef struct LStack
{
    Stack top;
    int length;
}LStack;
Status InitStack(LStack &S)
{
    S.top = (Stack)malloc(sizeof(StackNode));
    if (!S.top)
        exit(OVERFLOW);
    S.top->next = NULL;
    S.length = 0;
    return OK;
}
Status PushStack(LStack &S, SElemType e)
{
    Stack newnode = (Stack)malloc(sizeof(StackNode));
    if (!newnode)
        exit(OVERFLOW);
    newnode->data = e;
    newnode->next = S.top;
    S.top = newnode;
    ++S.length;
    return OK;
}
Status StackEmpty(LStack &S)
{
    if (S.length)
        return FALSE;
    else
        return TRUE;
}
Status PopStack(LStack &S, SElemType &e)
{
    if (StackEmpty(S))
        return ERROR;
    Stack p = S.top;
    e = p->data;
    S.top = p->next;
    free(p);
    p = NULL;
    --S.length;
    return OK;
}
Status DestroyStack(LStack &S)
{
    Stack p = S.top;
    while (p)
    {
        S.top = S.top->next;
        free(p);
        p = S.top;
    }
    S.length = 0;
    return OK;
}


Status Visit(TElemType e)
{
    printf("%c", e);
    return OK;
}
Status PreOrderTraverse1(BiTree T, Status (* Visit)(TElemType e))
{
    if (T)
    {
        Visit(T->data);
        PreOrderTraverse1(T->lchild, Visit);
        PreOrderTraverse1(T->rchild, Visit);
    }
    return OK;
}
Status PreOrderTraverse2(BiTree T, Status (* Visit)(TElemType e))
{
    LStack S;
    InitStack(S);
    BiTree p = T;
    while (p || !StackEmpty(S))
    {
        while (p)
        {
            Visit(p->data);
            PushStack(S, p);
            p = p->lchild;
        }
        PopStack(S, p);
        p = p->rchild;
    }
    return OK;
}
Status InOrderTraverse1(BiTree T, Status (* Visit)(TElemType e))
{
    if (T)
    {
        InOrderTraverse1(T->lchild, Visit);
        Visit(T->data);
        InOrderTraverse1(T->rchild, Visit);
    }
    return OK;
}
Status InOrderTraverse2(BiTree T, Status (*Visit)(TElemType e))
{
    LStack S;
    InitStack(S);
    BiTree p = T;
    while (p || !StackEmpty(S))
    {
        while (p)
        {
            PushStack(S, p);
            p = p->lchild;
        }
        PopStack(S, p);
        Visit(p->data);
        p = p->rchild;
    }
    DestroyStack(S);
    return OK;
}
Status PostOrderTraverse1(BiTree T, Status (* Visit)(TElemType e))
{
    if (T)
    {
        PostOrderTraverse1(T->lchild, Visit);
        PostOrderTraverse1(T->rchild, Visit);
        Visit(T->data);
    }
    return OK;
}
Status CreateBiTree(BiTree &T)
{
    int ch;
    scanf("%c", &ch);
    if (ch == ' ')
        T = NULL;
    else
    {
        if (!(T = (BiTree)malloc(sizeof(BiTNode))))
            exit(OVERFLOW);
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
    return OK;
}

int main(void)
{
    // TestData:ABC  DE G  F   #
    BiTree T;
    CreateBiTree(T);
    PreOrderTraverse1(T, Visit);
    printf("\n");
    PreOrderTraverse2(T, Visit);
    printf("\n");
    InOrderTraverse1(T, Visit);
    printf("\n");
    InOrderTraverse2(T, Visit);
    printf("\n");
    // PostOrderTraverse1(T, Visit);
    // printf("\n");

    return 0;
}